<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <script>
    /* 
      https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
      思路：
      1、二分法 && 两边向中间 https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/shuang-jie-fa-sou-suo-zuo-you-bian-jie-xun-huan-fa/
      2、暴力解法
     */
    let nums = [5,7,7,8,8,10], target = 8;

    // 1、二分法
    function search(nums, target) {
      let start = -1, end = -1;

      let left = 0, right = nums.length - 1;
      while (left <= right) {
        let mid = left + right >> 1;
        if (nums[mid] === target) {
          start = mid;
          right = mid - 1;
        } else if (nums[mid] > target) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      }

      left = 0, right = nums.length - 1;
      while (left <= right) {
        let mid = left + right >> 1;
        if (nums[mid] === target) {
          end = mid;
          left = mid + 1;
        } else if (nums[mid] > target) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      }

      return start <= end && start !== -1 ? end - start + 1 : 0;
    }

    // 2、两边向中间
    // function search(nums, target) {
    //   if (!nums.length) return 0;

    //   let left = 0, right = nums.length - 1;
    //   while (nums[left] !== target && left < nums.length) {
    //     left++;
    //   }
    //   while (nums[right] !== target && right >= 0) {
    //     right--;
    //   }

    //   return left <= right ? right - left + 1 : 0;
    // }

    // 3、暴力解法
    // function search(nums, target) {
    //   let times = 0;
    //   for (num of nums) {
    //     if (num === target) times++;
    //   }
    //   return times;
    // }
    console.log(search(nums, target));
  </script>
</body>
</html>